package com.future.interview;

import com.future.util.TreeNode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

/**
 * Description: 面试题 04.12. 求和路径
 * 定一棵二叉树，其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法，打印节点数值总和等于某个给定值的所有路径的数量。
 * 注意，路径不一定非得从二叉树的根节点或叶节点开始或结束，但是其方向必须向下(只能从父节点指向子节点方向)。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/paths-with-sum-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 示例:
 * 给定如下二叉树，以及目标和 sum = 22，
 * ------------- 5
 * -------------/ \
 * ------------4   8
 * ---------- /   / \
 * ----------11  13  4
 * ---------/  \    / \
 * --------7    2  5   1
 * 返回:
 * 3
 * 解释：和为 22的路径有：[5,4,11,2], [5,8,4,5], [4,11,7]
 *
 * @author weiruibai.vendor
 * Date: 2022/12/20 14:27
 */
public class Solution_0412 {

    private static Solution_0412 instance = new Solution_0412();

    public static void main(String[] args) {
        TreeNode head = new TreeNode(5);
        head.left = new TreeNode(4);
        head.right = new TreeNode(8);
        head.left.left = new TreeNode(11);
        head.left.left.left = new TreeNode(7);
        head.left.left.right = new TreeNode(2);
        head.right.left = new TreeNode(13);
        head.right.right = new TreeNode(4);
        head.right.right.left = new TreeNode(5);
        head.right.right.right = new TreeNode(1);
        int sum = 22;
        instance.pathSum_v2(head, sum);
        System.out.println("=====");
        instance.pathSum(head, sum);
    }

    int ans = 0;

    public int pathSum_v2(TreeNode root, int sum) {
        Set<List<Integer>> res = new HashSet<>();
        List<List<Integer>> paths = new ArrayList<>();
        process_v2(root, sum, res, paths);
        for (List list : res) {
            System.out.println(list);
        }
        return ans;
    }

    /**
     * 记录所有路径
     *
     * @param root
     * @param sum
     * @param res
     * @param paths
     */
    private void process_v2(TreeNode root, int sum, Set<List<Integer>> res, List<List<Integer>> paths) {
        if (root == null) {
            /**
             * 注意，需要把每个数组复制
             */
            Set<ArrayList<Integer>> collect = paths.stream().map(obj -> new ArrayList<>(obj)).collect(Collectors.toSet());
            res.addAll(collect);
            return;
        }
        int val = root.val;
        for (List list : paths) {
            list.add(val);
        }
        paths.add(new ArrayList<Integer>() {{
            add(val);
        }});
        process_v2(root.left, sum, res, paths);
        process_v2(root.right, sum, res, paths);
        // 恢复
        paths.remove(paths.size() - 1);
        for (List list : paths) {
            list.remove(list.size() - 1);
        }
    }

    public int pathSum(TreeNode root, int sum) {
        return process(root, sum, new ArrayList<>());
    }

    /**
     * 记录所有路径
     *
     * @param root
     * @param sum
     * @param paths
     */
    private int process(TreeNode root, int sum, List<Integer> paths) {
        if (root == null) {
            return 0;
        }
        int count = 0;
        int val = root.val;
        if (val == sum) {
            count++;
        }
        for (int i = 0; i < paths.size(); i++) {
            int newVal = paths.get(i) + val;
            if (newVal == sum) {
                count++;
            }
            paths.set(i, newVal);
        }
        paths.add(val);
        count += process(root.left, sum, paths);
        count += process(root.right, sum, paths);
        // 恢复
        paths.remove(paths.size() - 1);
        for (int i = 0; i < paths.size(); i++) {
            paths.set(i, paths.get(i) - val);
        }
        return count;
    }

}
